package hard.区间问题.合并区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 合并区间  Demo763是这题的升级版，这题比较简单
 * @date 2022/11/23 12:28
 */
public class Demo56 {
    public int[][] merge(int[][] intervals) {
        //根据起始位置排序，起始位置肯定不同，如果起始位置相同，则按照终止位置从大到小排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return o1[1]-o2[1];
                }
                return o1[0]-o2[0];
            }
        });
        //合并区间
        List<int[]> resList=new ArrayList<>();
        //只有一个元素，直接返回
        if(intervals.length==1){
            resList.add(new int[]{intervals[0][0],intervals[0][1]});
            return resList.toArray(new int[resList.size()][2]);
        }
        //多个元素合并区间
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i-1][1]>=intervals[i][0]){
                intervals[i][0]=Math.min(intervals[i-1][0],intervals[i][0]);
                intervals[i][1]=Math.max(intervals[i-1][1],intervals[i][1]);
            }else {
                resList.add(new int[]{intervals[i-1][0],intervals[i-1][1]});
            }
        }
        resList.add(new int[]{intervals[intervals.length-1][0],intervals[intervals.length-1][1]});
        return resList.toArray(new int[resList.size()][2]);
     }
}

